1. Field of the Invention
The invention relates to field of logic machines and methods for processing information within logic machines. In particular, the invention relates to electrical circuits and methods of using electrical circuits to evaluate logical relationships.
2. Description of the Prior Art
Efficient processing of Boolean expressions or complex logical signals has many applications in monitoring and debugging digital processes and hardware computing systems. Some other applications of Boolean evaluation are special purpose database search processors and hardware simulators for discrete systems.
The high-level monitoring activity involves the evaluation of Boolean functions based on the real-time behavior of the system being observed. Depending on the purpose of monitoring, different Boolean expressions are evaluated at different time intervals. The problem is how to develop an approach to evaluate an arbitrary Boolean expression in real-time. Some solutions to this monitoring problem include using a fixed set of Boolean expressions (fixed hardware tools), the manual rewiring of the monitor circuit (wired program tools), and the use of a high speed programmable monitor circuit (stored program tools). Stored program tools are the most flexible and satisfactory, but they impose a high cost on the monitor circuit because it must operate at a much faster rate than that of the system being observed.
One possibility of implementing a dynamically reconfigurable circuit that is able to evaluate any Boolean function of two variables is to use three, 2-input multiplexers. A 2-input multiplexer, is symbolically modeled by a Boolean function, M(a,b,s), which has two data inputs a and b, and one control signal s. It evaluates the function: EQU M(a,b,s)=as+bs.
Depending on the value of control signal s, input variable a or input variable b is chosen as the output of M. The function, M(a,b,s) can then be used to model an arbitrary logic circuit. For example, let F(x,y) be a Boolean function of two variables. Its value can be defined by: EQU F(0,0)=f.sub.0, EQU F(0,1)=f.sub.1, EQU F(1,0)=f.sub.2, EQU F(1,1)=f.sub.3.
It can be shown then that a function, F(x,y), is described by a Boolean expression: EQU F(x,y)=xyf.sub.0 +xyf.sub.1 +xyf.sub.2 +xyf.sub.3 ( 1)
Function F(x,y) in Equation (1) can be implemented by three, 2-input multiplexers as follows: EQU F(x,y)=M(M(f.sub.0,f.sub.2,x),M(f.sub.1,f.sub.3,x),y).
There are sixteen possible Boolean functions of the two variables which are listed in Table 1 below. In traditional Boolean function processing methods, all sixteen cases are represented by four bits of F(x,y), i.e., f0, f1, f2 and f3. Processing in a tree structure therefore becomes complex when implemented in custom hardware and very time and resource consumptive when implemented in a general purpose computer. In complex Boolean functions the processing time can seriously lag real time needs for the processed result unless the computing circuit is very large and very fast.
What is needed is an apparatus and methodology which will allow any kind of complex Boolean expression to be processed in a real time basis in small computer systems.